package com.squirrel.michale;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/24 7:44 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, result, 0);
        return result;
    }

    private void dfs(TreeNode cur, List<List<Integer>> res, int level) {
        if (cur == null)
            return;
        //如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
        if (res.size() <= level) {
            List<Integer> newLevel = new LinkedList<>();
            res.add(newLevel);
        }
        //遍历到第几层我们就操作第几层的数据
        List<Integer> list = res.get(level);
        //这里默认根节点是第0层，偶数层相当于从左往右遍历，
        // 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历，
        // 要把数据添加到集合的开头
        if (level % 2 == 0)
            list.add(cur.val);
        else
            list.add(0, cur.val);
        //分别遍历左右两个子节点，到下一层了，所以层数要加1
        dfs(cur.left, res, level + 1);
        dfs(cur.right, res, level + 1);
    }

//    作者：数据结构和算法
//    链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/solutions/530584/bfshe-dfsliang-chong-jie-jue-fang-shi-by-184y/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
